<?php
/**
 * @title 307. 区域和检索 - 数组可修改 - 线段树
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class NumArray {
    /**
     * @param Integer[] $nums
     */
    function __construct($nums) {
        /**
         * @since 2020-08-21 长度
         */
        $this->len = count($nums);

        /**
         * @since 2020-08-21 建树
         */
        $this->tree = [];
        for ($i=$this->len, $j=0; $j<$this->len; $i++, $j++){
            $this->tree[$i] = $nums[$j];
        }
        for($i=$this->len-1; $i>=1; $i--){
            $this->tree[$i] = $this->tree[$i*2] + $this->tree[$i*2+1];
        }
    }

    /**
     * @param Integer $i
     * @param Integer $val
     * @return NULL
     */
    function update($i, $val) {
        $i = $i+$this->len;

        /**
         * @since 2020-08-21 差值
         */
        $diffVal = $val-$this->tree[$i];

        /**
         * @since 2020-08-21 更新树
         */
        do{
            $this->tree[$i] += $diffVal;
            $i = $i>>1;
        }while($i>0);
    }

    /**
     * @param Integer $i
     * @param Integer $j
     * @return Integer
     */
    function sumRange($i, $j) {
        $sum = 0;

        $i = $this->len+$i;
        $j = $this->len+$j;
        while($j>=$i){
            if($i%2 == 1){
                $sum += $this->tree[$i];
                $i++;
            } else {}

            if($j%2 == 0){
                $sum += $this->tree[$j];
                $j--;
            } else {}

            $i = $i>>1;
            $j = $j>>1;
        }

        /**
         * @return
         */
        return $sum;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.20_4.php
 */
$datas = [
    [
        ["NumArray","sumRange","update","sumRange"],
        [[[1,3,5]],[0,2],[1,2],[0,2]],
    ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    $obj = new $data[0][0](...$data[1][0]);

    for ($i=1; $i<count($data[0]); $i++){
        $result = $obj->$data[0][$i](...$data[1][$i]);

        echo $data[0][$i] ."(\"". $data[1][$i][0] ."\") ";
        if($result === true){
            echo "True";
        } elseif($result === false) {
            echo "False";
        } elseif($result === null) {
            echo "Null";
        } elseif(is_array($result)) {
            var_dump($result);
        } else {
            echo $result;
        }
        echo PHP_EOL;
    }

    echo str_repeat(PHP_EOL, 3);
}
$xhprof->end();
